package com.itheima.erfen;

import org.junit.jupiter.api.Test;

public class great {
    //局部最小问题，摒弃二分查找只能在有序数组中使用的想法
    //局部最小：对于一个数来说比左右两边的数都小，那么这个数就是局部最小的，对于边界只要小于倒数第二个数即可
    //题目：在一个数组中，相邻元素都不相等（必定存在低谷即局部最小）,找出一个局部最小（其实找出所有也可以，我认为可以使用递归实现）

    @Test
    public void greatTest(){
        int arr[] = {1};
        serch(arr);

    }

    private void serch(int[] arr){
        if(arr == null || arr.length < 2){
            System.out.println("传入数组不对，应有值且至少有两个值");
            return;
        }
        //首先判断首位处是否符合要求
        if(arr[0] < arr[1]){
            System.out.println("局部最小为索引0");
            return;
        }
        //判断末尾处是否符合要求
        if(arr[arr.length - 1] < arr[arr.length - 2]){
            System.out.println("局部最小为索引" + (arr.length - 1));
            return;
        }
        //首位不符合要求则首部乘递减而尾部乘递增，则中间必有某处存在局部最小（相邻元素不等前提下）
        //使用二分查找判断中间值
        int left = 1;
        int right = arr.length - 2;
        while (left <= right){
            int mid = left + ((right - left) >> 1);
            //可以认为如果mid小于其左边的值且小于其右边的值则mid为局部最小，但mid如果大于其左边的值则由于首部为递减此处为递增，中间必有局部最小，右边也一样
            if(arr[mid] > arr[mid - 1]){
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else if (arr[mid - 1] > arr[mid] && arr[mid] < arr[mid + 1]) {
                System.out.println("局部最小为索引" + mid);
                return;
            }else {
                System.out.println("数组值有问题");
                return;
            }
        }
    }

    // 对数器：用于验证算法的正确性
    @Test
    public void logarithmicDetector() {
        int testTime = 500000; // 测试次数
        int maxSize = 100; // 数组最大长度
        int maxValue = 100; // 数组元素的最大值
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            // 确保相邻元素不相等
            for (int j = 1; j < arr.length; j++) {
                while (arr[j] == arr[j - 1]) {
                    arr[j] = (int) (Math.random() * maxValue) + 1;
                }
            }
            int result = findLocalMinimum(arr);
            if (!checkLocalMinimum(arr, result)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }

    // 生成随机数组
    private int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((Math.random() * maxSize) + 1)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((Math.random() * maxValue) + 1);
        }
        return arr;
    }

    // 查找局部最小值索引
    private int findLocalMinimum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return -1;
        }
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1;
        int right = arr.length - 2;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else if (arr[mid - 1] > arr[mid] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                return -1;
            }
        }
        return -1;
    }

    // 验证局部最小值是否正确
    private boolean checkLocalMinimum(int[] arr, int index) {
        if (index == -1) {
            return false;
        }
        if (arr.length == 1) {
            return true;
        }
        if (index == 0) {
            return arr[index] < arr[index + 1];
        }
        if (index == arr.length - 1) {
            return arr[index] < arr[index - 1];
        }
        return arr[index] < arr[index - 1] && arr[index] < arr[index + 1];
    }
}
